package _2021._8._264_丑数II;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 264
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 */
public class Solution {
    //2. 使用优先队列(最小堆)
    public int nthUglyNumber2(int n) {
        int[] factors = {2, 3, 5};
        int ans = 0;
        Set<Long> seen = new HashSet<>();
        PriorityQueue<Long> heap = new PriorityQueue<>();
        seen.add(1L);
        heap.offer(1L);
        for (int i = 0; i < n; i++) {
            //取出堆中的最小值
            long curr = heap.poll();
            ans = (int) curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (seen.add(next)) {
                    heap.offer(next);
                }
            }
        }
        return ans;
    }

    //1. 超时
    public int nthUglyNumber(int n) {
        int i = 1, ans = 1, count = 0;
        int[] factors = {2, 3, 5};
        while (count < n) {
            int tmp = i;
            for (int factor : factors) {
                while (tmp % factor == 0) {
                    tmp /= factor;
                }
            }
            if (tmp == 1) {
                count++;
                ans = i;
            }
            i++;
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().nthUglyNumber2(1690));
    }
}
